package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

//https://leetcode-cn.com/problems/word-ladder/solution/wu-quan-tu-de-yan-sou-wen-ti-xiang-xi-ti-jie-kan-d/
public class Code16_WordLadder {

	public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
		Queue<String> queue = new LinkedList<>();
		Set<String> isVisited = new HashSet<>();
		// 建立一个图，里面存字典里所有的字符（包括beginword）可以直接达到的字符串
		Map<String, List<String>> map = new HashMap<>();
		wordList.add(beginWord);
		for (String s : wordList) {
			map.put(s, change1Bit(wordList, s));
		}
		queue.offer(beginWord);
		int count = 1;
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int m = 0; m < size; m++) {
				String cur = queue.poll();
				isVisited.add(cur);

				if (cur.equals(endWord)) {
					return count;
				}
				// System.out.println(cur);
				// System.out.println(change1Bit(wordList,cur));
				for (String c : map.get(cur)) {
					if (isVisited.contains(c)) {
						continue;
					}
					queue.offer(c);
				}
			}

			count++;
		}
		return 0;
	}

	// 给定一个字符串s，一个字典wordList，从字典中找出所有s变化1位后能变成的结果
	public static List<String> change1Bit(List<String> wordList, String s) {
		List<String> list = new ArrayList<>();
		int len = s.length();
		for (String c : wordList) {
			int count = 0;
			for (int i = 0; i < len; i++) {
				if (c.charAt(i) != s.charAt(i)) {
					count++;
				}
				// 如果有两位不一致，这个字符c就不满足条件，直接跳到下一个字符
				if (count == 2) {
					break;
				}
			}
			// 遍历完c后如果不一致位小于2，就把c加入到list中
			if (count < 2) {
				list.add(c);
			}
		}
		return list;
	}

	public static void main(String[] args) {
		String beginWord = "hit";
		String endWord = "cog";
		List<String> wordList = new ArrayList<String>();
//		{"hot","dot","dog","lot","log","cog"};
		wordList.add("hot");
		wordList.add("dot");
		wordList.add("dog");
		wordList.add("lot");
		wordList.add("log");
		wordList.add("cog");

		int count = ladderLength(beginWord, endWord, wordList);
		System.out.println(count);
	}

}
